package com.singzi.leetcode.N100;

public class T0076 {
    public static void main(String[] args) {
        String s = "aa";
        String t = "aa";
        Solution0076 solution0076 = new Solution0076();
        System.out.println(solution0076.minWindow(s, t));
    }
}
class Solution0076 {
    public String minWindow(String s, String t){
        if(t.length() > s.length()) return "";
        boolean flag = false;
        int []letters = new int[52];
        getLetters(letters, t);
        int n = s.length();
        int left = 0, right = 0, start = 0,end = 0;
        while (right < n){
            letters[getIndex(s.charAt(right))]--;
            if(isZero(letters)) {
                flag = true;
                break;
            }
            right++;
        }
        //二分法可再优化下
        end = right;
        int min = right - left+1;
        if(min  == t.length()) return s.substring(start, end+1);
        while (right < n){
            while (left < n && letters[getIndex(s.charAt(left))]+1 <= 0){
                letters[getIndex(s.charAt(left))]++;
                left++;
                if(right - left + 1 < min) {
                    min = right - left + 1;
                    start = left;
                    end = right;
                }
                if(min  == t.length()) return s.substring(start, end+1);
            }
            right++;
            if(right < n)  letters[getIndex(s.charAt(right))]--;
        }
        if(!flag) return "";
        return s.substring(start, end+1);
    }
    public boolean isZero(int[] letters){
        for (int letter : letters) {
            if (letter > 0) return false;
        }
        return true;
    }
    public int getIndex(char letter){
        if(letter >= 'a'){
            return  letter - 'a' + 26;
        }else {
            return letter - 'A';
        }
    }
    private void getLetters(int[] letters, String t) {
        for (int i = 0; i < t.length(); i++) {
            letters[getIndex(t.charAt(i))]++;
        }
    }
}